#ifndef ITERATOR_DEF_H
#define ITERATOR_DEF_H

/*
    模仿STL迭代器
    重点实现他的萃取机制
*/

#include <type_traits.hpp>
#include <type_traits>

namespace TingSTL {

/**
 *  迭代器 萃取原理
 *  tag继承关系表示包含关系
 * 后续使用is_convertible（判断两个类型是否能够相互转换，编译期判断）判断
 * 迭代器类型 https://zh.cppreference.com/w/cpp/language/sfinae
 *  https://en.cppreference.com/w/cpp/types/is_convertible
 *   https://zh.cppreference.com/w/cpp/types/enable_if
 */

// 五种迭代器 TAG
struct input_iterator_tag {};  // 输入迭代器
struct output_iterator_tag {}; // 输出迭代器
struct forward_iterator_tag : public input_iterator_tag,
                              public output_iterator_tag {}; // 向前迭代器
struct bidirectional_iterator_tag : public forward_iterator_tag {
}; // 双向迭代器
struct random_access_iterator_tag : public bidirectional_iterator_tag {
}; // 随机访问迭代器

// 所有迭代器的基类
template <typename Category, typename T, typename Distance = ptrdiff_t,
          typename Pointer = T *, typename Reference = T &>
struct base_iterator {
    using iterator_category = Category; // 类别
    using value_type = T;               // 值类型
    using pointer = Pointer;            // 指针类型
    using reference = Reference;        // 引用类型
    using difference_type = Distance;   // 迭代器距离
};

// ///////////////////////////// 对迭代器进行萃取 /////////////////////////////
// 迭代器类型萃取器
template <typename Iterator>
struct iterator_traits {
    // 不写 typename C4346:  如果将依赖名称视为类型，则 typename 关键字是必需的
    using iterator_category = typename Iterator::iterator_category;
    using value_type = typename Iterator::value_type;
    using pointer = typename Iterator::pointer;
    using reference = typename Iterator::reference;
    using difference_type = typename Iterator::difference_type;
};

// 针对普通指正进行模版特化
template <typename T>
struct iterator_traits<T *> {
    using iterator_category = random_access_iterator_tag;
    using value_type = T;
    using pointer = T *;
    using reference = T &;
    using difference_type = size_t;
};

template <typename T>
struct iterator_traits<const T *> {
    using iterator_category = random_access_iterator_tag;
    using value_type = T;
    using pointer = const T *;
    using reference = const T &;
    using difference_type = size_t;
};

// 判断是否为 输入迭代器
template <typename Iter>
struct is_input_iterator
    : public bool_constant<
          std::is_convertible<typename iterator_traits<Iter>::iterator_category,
                              input_iterator_tag>::value> {};

// 判断是否为 输出迭代器
template <typename Iter>
struct is_output_iterator
    : public bool_constant<
          std::is_convertible<typename iterator_traits<Iter>::iterator_category,
                              output_iterator_tag>::value> {};

// 判断是否为 向前迭代器
template <typename Iter>
struct is_forward_iterator
    : public bool_constant<
          std::is_convertible<typename iterator_traits<Iter>::iterator_category,
                              forward_iterator_tag>::value> {};

// 判断是否为 双向迭代器
template <typename Iter>
struct is_bidirectional_iterator
    : public bool_constant<
          std::is_convertible<typename iterator_traits<Iter>::iterator_category,
                              bidirectional_iterator_tag>::value> {};

// 判断是否为 随机迭代器
template <typename Iter>
struct is_radom_iterator
    : public bool_constant<
          std::is_convertible<typename iterator_traits<Iter>::iterator_category,
                              random_access_iterator_tag>::value> {};

// ///////////////////////////// 迭代器 常用算法 /////////////////////////////
//  计算迭代器之间的距离
template <typename RandomIter>
typename iterator_traits<typename RandomIter>::difference_type
distance(const RandomIter &lhs, const RandomIter &rhs,
         random_access_iterator_tag) {
    return rhs - lhs;
}

template <typename RandomIter>
typename iterator_traits<typename RandomIter>::difference_type
distance(const RandomIter &lhs, const RandomIter &rhs, forward_iterator_tag) {
    iterator_traits<typename RandomIter>::difference_type ret = 0;
    while (lhs != rhs) {
        ++lhs;
        ++ret;
    }
    return ret;
}

template <typename Iter>
typename iterator_traits<typename Iter>::difference_type
distance(const Iter &lhs, const Iter &rhs) {
    return distance(lhs, rhs,
                    iterator_traits<typename Iter>::iterator_category);
}

// 判断是否具有迭代器
template <typename T, typename CheckType = void_t<>>
struct has_iterator : public false_type {};

template <typename T>
struct has_iterator<T, typename void_t<typename T::iterator>>
    : public true_type {};

template <typename T>
using has_iterator_v = typename has_iterator<T>::value;

// ///////////////////////////// 反向迭代器的实现 /////////////////////////////

} // namespace TingSTL

#endif // ITERATOR_DEF_H